package com.yulan.dp.gupiao;

import org.junit.Test;

/**
 * 123. 买卖股票的最佳时机 III
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 */
public class LeetCode_123 {
    /**
     *
     * Dp[i][k][0 or 1 ] 表示 第i天还剩k次交易次数，1持有，0不持有
     * 状态转移：Dp[i][k][0] = max(Dp[i-1][k][0] , Dp[i-1][k-1][1] + prices[i])
     *           Dp[i][k][1] = max(Dp[i-1][k][1], Dp[i-1][k-1][0] - prices[i])
     */
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int max_k = 2;
        int n = prices.length;
        int[][][] dp = new int[n][max_k+1][2];
        dp[0][2][0] = 0;
        dp[0][2][1] = -prices[0];
        dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];
        for(int i = 0; i<n; i++){
            for(int k = max_k; k >= 1; k--){
                if(i - 1 == -1) continue;
                dp[i][k][0] = Math.max(dp[i-1][k][0],dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
        }
        return dp[n-1][max_k][0];
    }

    @Test
    public void test(){
        int[] arr = {3,2,6,5,0,3};
        System.out.println(maxProfit(arr));
    }
}
